//139 Word Break
/*
给定一个字符串和一个字符串集合，求是否存在一种分割方式，使得原字符串分割后的子字
符串都可以在集合内找到

输入输出样例
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
在这个样例中，字符串可以被分割为 [“apple” ,“pen” ,“apple” ]
*/
bool wordBreak(string s, vector<string> &wordDict)
{
	int n = s.length();
	vector<bool> dp(n + 1, false);
	dp[0] = true;
	for (int i = 1; i <= n; ++i)
	{
		for (const string &word : wordDict)
		{
			int len = word.length();
			if (i >= len && s.substr(i - len, len) == word)
			{
				dp[i] = dp[i] || dp[i - len];
			}
		}
	}
	return dp[n];
}
